The invention relates to First-in, First-out (FIFO) devices and queuing schemes for data communication systems using frames of data.
Frame Relay (FR) networks route FR frames, using a plurality of frame-relay frame handlers, from one terminal equipment station to another. The FR frame structure is defined by American National Standards Institute (ANSI) Standard T1.618. Based on the High-level Data Link Control (HDLC) protocol, frame relay frames are delimited by one or more flags. To avoid data being incorrectly interpreted as a flag, frames of data are xe2x80x9cstuffedxe2x80x9d prior to transmission using a zero bit insertion algorithm. More specifically, data in FR frames are transported using the following standard HDLC framing:
 less than flag greater than  less than data greater than  less than crc greater than  less than flag greater than 
where
 less than flag greater than  is the bit sequence 01111110,
 less than data greater than  is the frame payload (not restricted to just exactly byte sized dataxe2x80x94the data may for example be 25 bits long).
 less than crc greater than  is the 16 bit cyclic redundant check (CRC) character of the  less than data greater than  section.
Should the bit sequence 01111110 appear in the data stream, it would be incorrectly interpreted as a flag sequence. To overcome this, every time the sequence 11111 appears in the data, an extra xe2x80x980xe2x80x99 is inserted (xe2x80x98stuffedxe2x80x99) into the data stream, i.e., it is replaced with 111110. On reception the converse occursxe2x80x94the sequence 111110 is replaced with 11111 (xe2x80x98de-stuffedxe2x80x99) after the flag detection logic. Consequently, the 8 bit sequence 01111110 in the data would be transmitted as a 9 bit sequence 011111010.
This bit stuffing has significant impact on the rate which data can be transmitted. Take for example two different data frames of 256 bytes. One contains all zeros, and the other contains all 1""s. The frame containing all zeroes will have no bit stuffing applied (as the sequence 11111 will not occur, except maybe in the CRC), and the entire frame will be (256 * 8)+32=2080 bits. The frame containing all 1""s will have an extra 0 inserted every 5 data bits, and the entire frame will therefore be (256 * 8)+((256 * 8)/5)+32=2489 bits. Given the line bit rate is fixed, the all 1""s frame will take almost 20% longer to transmit.
For in-line frame relay equipment, the data is received on one port and transmitted on another. In such equipment, when the frames are simply transferred from the receiver to the transmitter (i.e., in plaintext bypass conditions), this variability in the effective transmission rate has no major impact. In other words, for a given item of data, the level of bit stuffing on the receiver and transmitter will match. However, when the data is modified, the level of bit stuffing for the receiver and transmitter may be different. For example, when data is encrypted, the encrypted data is essentially random (The data bits 0/1 distribution is statistically identical to the head/tail results from tossing a coin many times). This has the effect that with the above-mentioned, illustrative 256 byte frame, when encrypted, has generally between 30 and 40 stuffing bits inserted (i.e., 2110 to 2120 bits in the total frame size), regardless of the number of stuffing bits that were present in the unencrypted data.
Although frame relay (and most other systems using HDLC framing) do not support payloads that are not exact bytes in size, the HDLC standard is designed to cope with this possibility. Therefore, the flag bit-stuffing mechanism operates on every bit in the data stream, not just at the byte boundaries.
Commercially available products, such as the product identified by the trademark xe2x80x9cDC2K-FRxe2x80x9d and manufactured by Racal-Airtech Limited, a U.K. company, xe2x80x9cdestuffxe2x80x9d each frame (i.e., removes the zero bits added by the stuffing process), transform it (e.g., by encryptionxe2x80x94when required) and re-stuff it before transmitting. Since the data being re-stuffed has been transformed, it may have very different statistical characteristics to the original frame, and a different number of bits may be added by the restuffing process than were removed during the destuffing process, causing the unit""s input and output data rates to be different.
In these commercially available products, an xe2x80x9cequalizingxe2x80x9d First-in First-out device (FIFO) is used to minimise the loss and corruption of frames due to this effect. In the equalizing FIFO, the next byte to be retrieved is the byte that has been in the queue for the longest time. The equalizing FIFO used is fairly large, having to cope with potentially very different input and output data rates. Encrypted data is essentially random, whereas the input data that is destuffed can be highly formatted (Word documents, for example, have a large number of 1""s in their binary image, requiring a relatively large amount of de-stuffing).
With respect to the above referenced DC2K-FR encryption unit, the equalizing FIFO is used in the following manner. The length of the FIFO used is 512 bytes, and a xe2x80x9cwatermarkxe2x80x9d typically, for example, is set at 90 bytes to allow for an underrun (where data transmitted has less stuffing than that received) of up to 90 bytes, or an overrun (where data received has less stuffing than that transmitted) of up to 512xe2x88x9290=422 bytes. The frames coming into the encryption unit are not passed out of the encryption unit until either at least 90 bytes of the frame have been received by the equalizing FIFO, or the entire frame has been received, causing a (non-cumulative) latency in data output. Other features of this design (the encryption algorithm for example) also cause some degree of latency, giving rise to a total latency of approximately 15 plus minimum (90 bytes or length of frame in bytes).
As implemented in this prior art design, the watermark is calculated to avoid an underrun for a given maximum size data frame. For example, to allow a 1500 byte frame, the watermark would need to be set to at least 275 bytes. More specifically, this watermark value can be calculated as follows. The worst case situation is for this 1500 byte frame, as received by the FIFO, to have all ones, which will lead to the frame being bit stuffed at the rate one stuffing bit per 5 data bits (20%), giving a total frame length of 1800 bytes (=1500 * 1.2) on the receive side of the FIFO. On encrypted data, the stuffing rate is around 1 bit per 60 data bits (1.7%), giving a total frame length of 1525 bytes (=1500 * 1.017) on the transmit side. The watermark in the FIFO must be set so that the frame will have finished being received before it has finished being retransmitted; hence, the watermark must be at least 275 (1800-1525) bytes. This approach has a number of problems, as described below:
1. The system ends up with an artificially large latency on all but small frames.
2. The amount of FIFO space available to handle overrun conditions is reduced.
3. There is no mechanism to handle larger highly stuffed frames.
The invention is directed toward a method of buffering received frames of data bits comprising the steps of inputting the data bits into a first-in first-out buffer at a first data rate; outputting the data bits from the buffer at a second data rate when a complete frame of the data bits has been received by the buffer or the amount of the data bits received by the buffer reaches a watermark, detecting when the buffer has an underrun condition or an overrun condition, wherein the improvement is characterised by the following steps of increasing the watermark by a first predetermined amount when the underrun condition is detected; and decreasing the watermark by a second predetermined amount when the overrun condition is detected.
The invention is also directed to a frame processing device for processing received frames of data bits comprising means for receiving the data bits with a first data rate; data manipulation means being operable for changing the amount of the data bits; means for transmitting the data bits with a second data rate; first-in first-out (FIFO) buffer means for compensating for a rate difference between the first data rate and the second data rate; and the FIFO buffer means including output means for outputting the data bits from the FIFO buffer means when a complete frame of the data bits has been received by the FIFO buffer means or amount of the data bits received by the FIFO buffer reaches a watermark and detection means for detection when the FIFO has an underrun condition or an overrun condition, wherein the improvement is characterised by the FIFO buffer means including underrun means for increasing the watermark by a first predetermined amount when the detection means detects the underrun condition; and the FIFO buffer means including overrun means for decreasing the watermark by a second predetermined amount when the detection means detects the overrun condition.
The features of the invention believed to be novel are set forth with particularity in the appended claims. The invention itself, however, both as to organization and method of operation, together with further objects and advantages thereof, may be best understood by reference to the following description taken in conjunction with the accompanying drawing.